package problems.practice;

import java.util.Arrays;

/**
 * 935. 骑士拨号器
 * <p>https://leetcode.cn/problems/knight-dialer/</p>
 *
 * @author habitplus
 * @since 17:41, 2022/10/6
 */
public class T935 {

    int[][] from = {
            {4, 6}, // 到达 0 的键
            {6, 8}, // 到达 1 的键
            {7, 9}, // 到达 2 的键
            {4, 8}, // 到达 3 的键
            {0, 3, 9}, // 到达 4 的键
            {},
            {0, 1, 7}, // 到达 6 的键
            {2, 6}, // 到达 7 的键
            {1, 3}, // 到达 8 的键
            {2, 4}, // 到达 9 的键

    };

    static final int MOD = (int) (1e9 + 7);

    public int knightDialer1(int n) {
        if (n < 2) return n < 1 ? 0 : 10;

        int [] dp = new int[10];
        int[] tmpArr = new int[10];
        int m = dp.length;

        // 第 i 步到达0, 1, 2, ..., 9 的步数
        Arrays.fill(dp, 1);
        dp[5] = 0;

        while(--n > 0) {
            System.arraycopy(dp, 0, tmpArr, 0, m);

            for (int j = 0; j < m; ++j) {
                if(j == 5) continue;
                dp[j] = 0;
                for (int k : from[j]) dp[j] = (dp[j] + tmpArr[k]) % MOD;
            }
        }

        long ret = 0L;
        for (int a : dp) ret += a;

        return (int) (ret % MOD);
    }

    /**
     * 动态规划 + 状态压缩
     */
    public int knightDialer(int n) {
        if (n < 2) return n == 1 ? 10 : 0;

        // 根据对称性：
        // 1, 3, 7, 9 为一组，即 g1
        // 2, 8 为一组，即 g2
        // 4, 6 为一组，即 g3
        // 0 为一组，即 g4
        long g1 = 4, g2 = 2, g3 = 2, g4 = 1;
        long tmp1, tmp2;

        for (int i = 1; i < n; ++i) {
            // 计算 g1，以到达 1 为例，则上一步应该在 8 or 6
            // 因此当前到达 1 的有效跳跃数为 (g2 / 2 + g3 / 2)
            // 由于 1,3,7,9 等价，因此 g1 = (g2 / 2 + g3 / 2) * 4
            tmp1 = ((g2 + g3) * 2) % MOD;

            // 同理，计算 g3 = (g4 + g1 / 4 * 2) * 2
            tmp2 = (2 * g4 + g1) % MOD;

            // 同理，计算 g2 = (g1 / 4 + g1 / 4) * 2
            g2 = g1 % MOD;

            // 同理，计算 g4 = (g3 / 2 + g3 / 2)
            g4 = g3 % MOD;

            g1 = tmp1;
            g3 = tmp2;
        }

        return (int) ((g1 + g2 + g3 + g4) % MOD);
    }

    public static void main(String[] args) {
        System.out.println(new T935().knightDialer(3131));
        System.out.println((int) (1e9 + 7));
    }
}
